package q134_canCompleteCircuit;

public class Solution_1 {
    public static void main(String[] args) {
        Solution_1 s = new Solution_1();
        System.out.println(s.canCompleteCircuit(new int[]{5, 1, 2, 3, 4}, new int[]{4,4,1,5,1}));
    }

    /**
     * 该算法检验过多，超时
     * @param gas
     * @param cost
     * @return
     */
    public int canCompleteCircuit(int[] gas, int[] cost) {
        for (int i = 0; i < gas.length; i++) {
            if (gas[i] < cost[i]) {
                continue;
            }
            if (canComplete(gas, cost, i)) {
                return i;
            }
        }
        return -1;
    }

    public boolean canComplete(int[] gas, int[] cost, int startIndex) {
        int leftGas = 0;
        for (int i = startIndex; i < gas.length; i++) {
            leftGas = leftGas + gas[i] - cost[i];
            if (leftGas < 0) {
                return false;
            }
        }
        for (int i = 0; i < startIndex; i++) {
            leftGas = leftGas + gas[i] - cost[i];
            if (leftGas < 0) {
                return false;
            }
        }
        return true;
    }
}
